package com.example.algorithm.no0003.solution;

import com.example.algorithm.no0003.Solution;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description 解答-无重复字符的最长子串-Map
 * @ClassName MapSolution
 * @Author Administrator
 * @Date 2020/5/20 10:26
 * @Version 1.0.0
 */
public class MapSolution implements Solution {
    @Override
    public int lengthOfLongestSubstring(String s) {
        // 定义 maxLength 记录无重复字符子串的最大长度
        int maxLength = 0;

        // 定义 HashMap 记录遍历到字符以及在原字符串中索引的对应关系。
        Map<Character, Integer> map = new HashMap<>();

        for (int right = 0, left = 0; right < s.length(); right++) {
            if (map.containsKey(s.charAt(right))) {
                // 根据重复字符是否在当前遍历子串中来判断是否需要更新左指针。
                left = Math.max(map.get(s.charAt(right)), left);
            }
            // 每次遍历记录到当前位置无重复字符子串的最大长度。
            maxLength = Math.max(maxLength, right - left + 1);
            // 每次更新遍历到的字符与当前索引的对应关系存入 HashMap 。
            map.put(s.charAt(right), right + 1);
        }
        return maxLength;
    }
}
